import random
import numpy as np
import turtle as t
import copy
import math
import matplotlib.pyplot as plt

# 随机数
# r1 = random.randint(0, 50)
# r2 = random.randint(0, 50)

maxTimes = 2000  # 最大迭代次数
indivi_num = 500  # 初始个体数目(染色体数目)
max_indivi_num = 50  # 个体数目最大值
chromo_length = 30  # 染色体长度（城市数目/基因数目）
survive_num = 300  # 选择次数
"""
城市编号0~chromo_length-1
"""
information = {0: [41, 94], 1: [37, 84], 2: [53, 67], 3: [25, 62], 4: [7, 64],
               5: [2, 99], 6: [68, 58], 7: [71, 44], 8: [54, 62], 9: [83, 69],
               10: [64, 60], 11: [18, 54], 12: [22, 60], 13: [83, 46], 14: [91, 38], 15: [25, 38], 16: [24, 42],
               17: [58, 69], 18: [71, 71], 19: [74, 78], 20: [87, 76], 21: [18, 40], 22: [13, 40], 23: [82, 7],
               24: [62, 32], 25: [58, 35], 26: [42, 21], 27: [41, 26],
               28: [44, 35], 29: [4, 50]}
start = 0  # 规定起点
crossRate = 0.7  # 交叉概率
crossNum = 100  # 交叉次数
variationRate = 0.5  # 变异概率


# 计算两个城市间的距离
def distance(city1, city2):
    [x1, y1] = information[city1]
    [x2, y2] = information[city2]
    d = np.sqrt(np.square(x1 - x2) + np.square(y1 - y2))
    return d


# 每个个体代表的距离
def total_distance(individual):
    sum_distance = 0
    for ii in range(chromo_length - 1):
        sum_distance = sum_distance + distance(individual[ii], individual[ii + 1])
    sum_distance = sum_distance + distance(individual[0], individual[9])  # 加上首尾相连的距离
    return sum_distance


# 计算适应度
def adaptability(individual):
    sum_distance = 0
    for ii in range(chromo_length - 1):
        sum_distance = sum_distance + distance(individual[ii], individual[ii + 1])
    sum_distance = sum_distance + distance(individual[0], individual[9])  # 加上首尾相连的距离
    # return 1 / (sum_distance * sum_distance)
    return 1 / sum_distance


# 选择
def choose(population):
    # 计算每个个体的适应度，及适应度总和
    adapt = []
    sum_adapt = 0
    for i in range(len(population)):
        adapt.append(adaptability(population[i]))
        sum_adapt = sum_adapt + adapt[i]
    # print(adapt)
    # 计算每个个体被选择概率
    choiceRate = []
    for j in range(len(population)):
        choiceRate.append(adapt[j] / sum_adapt)
    # print(choiceRate)
    # 计算轮盘上的累积概率
    cumulateRate = []
    for ii in range(len(population)):
        if ii == 0:
            cumulateRate.append(choiceRate[0])
        else:
            temp_sum = 0
            for jj in range(ii + 1):
                temp_sum = temp_sum + choiceRate[jj]
            cumulateRate.append(temp_sum)
    # print(cumulateRate)
    # 开始轮盘赌选择
    chosen = []  # 存放被选中的个体
    for k in range(survive_num):
        # while len(chosen)< len(population)//2:
        r = random.random()
        if r <= cumulateRate[0] and ((0 in chosen) is False):
            chosen.append(0)
        else:
            for kk in range(len(population) - 1):
                if (cumulateRate[kk] < r <= cumulateRate[kk + 1]) and ((kk + 1 in chosen) is False):
                    chosen.append(kk + 1)
                    break

    # print(chosen)
    return chosen


# 交叉
def cross(cross_num, chosen_chromo, population):
    child = []
    for i in range(crossNum):
        # 父代
        r1 = random.randint(0, cross_num - 1)
        r2 = random.randint(0, cross_num - 1)
        parents1 = population[chosen_chromo[r1]]
        parents2 = population[chosen_chromo[r2]]
        child1 = []
        child2 = []
        r = random.randint(0, 100) / 100  # 用于判断是否交叉
        # 是否交叉由交叉概率决定
        if r <= crossRate:
            # 随机产生左右两个交叉点位
            r1 = random.randint(1, chromo_length - 2)
            r2 = random.randint(r1, chromo_length - 1)
            fragment1 = parents1[r1:r2 + 1]
            fragment2 = parents2[r1:r2 + 1]
            temp1 = parents1[r2 + 1:] + parents1[:r2 + 1]
            temp2 = parents2[r2 + 1:] + parents2[:r2 + 1]
            for ele in fragment2:
                temp1.remove(ele)
            for ele in fragment1:
                temp2.remove(ele)
            child1 = temp1[len(parents1) - r2 - 1:] + fragment2 + temp1[:len(parents1) - r2 - 1]
            child2 = temp2[len(parents2) - r2 - 1:] + fragment1 + temp2[:len(parents2) - r2 - 1]
            # 统一起点
            for j, g in enumerate(child1):
                if g == start:
                    child1[0], child1[j] = child1[j], child1[0]
                    break
            # 统一起点
            for j, g in enumerate(child2):
                if g == start:
                    child2[0], child2[j] = child2[j], child2[0]
                    break
            if len(child1) != 0:
                child.append(child1)
            if len(child2) != 0:
                child.append(child2)

    return child


# 变异
def variation(population):
    for i in range(len(population)):
        r = random.randint(0, 100) / 100  # 用于判断是否变异
        if r <= variationRate:
            r1 = random.randint(1, chromo_length - 1)
            r2 = random.randint(1, chromo_length - 1)
            population[i][r1], population[i][r2] = population[i][r2], population[i][r1]
    return population


def drawPath(list):
    t.pensize(3)
    t.hideturtle()
    t.colormode(255)
    t.setup(510, 510)
    t.up()

    t.speed(10)
    for x, y in list:
        t.goto((x * 5 - 250), (y * 5 - 250))
        t.down()
        t.dot(7, "purple")
        t.color((255, 155, 192), "pink")
    t.done()


# 种群初始化
population = []  # 种群
for i in range(indivi_num):
    chromo = list(range(chromo_length))
    np.random.shuffle(chromo)
    # 统一起点
    for j, g in enumerate(chromo):
        if g == start:
            chromo[0], chromo[j] = chromo[j], chromo[0]
            break
    population.append(chromo)
# print(population)
last_min = 0
generation = 0
best = []
last_best = []
min_list = []
min_list_show = []
for i_gene in range(maxTimes):
    parents = []
    chosen = choose(population.copy())  # 选择操作
    # print(chosen)
    childs = cross(len(chosen), chosen.copy(), population.copy())  # 交叉操作
    for ele in chosen:
        parents.append(population[ele].copy())
    population = parents + childs  # 父代与子代形成新的种群
    population = variation(population.copy())  # 变异操作
    population = variation(population.copy())  # 变异操作
    population = variation(population.copy())  # 变异操作
    if len(last_best) != 0:
        population.append(last_best)  # 保留上一个最优解
    Distance = []
    for i in range(len(population)):
        Distance.append(total_distance(population[i].copy()))
    # 找最小值
    index = 0
    for j in range(len(Distance)):
        if Distance[j] < Distance[index]:
            index = j
    print('迭代次数: ', i_gene, '  种群规模: ', len(Distance), end=' ')
    min_distance = Distance[index]
    print('  min: ', math.floor(min_distance))
    last_best = population[index]  # 保留此次的最优解
    if i_gene == 0:
        last_min = min_distance
    else:
        if math.floor(min_distance) < math.floor(last_min):
            last_min = min_distance
            generation = i_gene
            best = population[index]
            min_list = []
            min_list.append(min_distance)
            crossRate = 0.7
            variationRate = 0.5
            # crossNum = 100
            survive_num = 300
        else:
            min_list.append(min_distance)

    if len(min_list) > 30:
        crossRate = 0.9
        variationRate = 0.9
        survive_num = 600
        # crossNum += 50
        print('change')

    min_list_show.append(last_min)

    if len(population) == 0:
        break

print('代数', generation)
print('最短路程', math.floor(last_min))
print('最优解', best)

# 画图
plt.ylim(400, 1200)
plt.plot(range(len(min_list_show)), min_list_show, color='green', label='training accuracy')
plt.show()

result = []
for ii in best:
    result.append(information[ii])
drawPath(result)

print('finish')
# print(population)
